package binarytree;

import java.util.Arrays;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/22 0:37
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
 */
public class BuildTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 递归  每次递归都会定义新的数组，耗时，占空间
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) {
            return null;
        }
        //1、后序数组最后一个结点作为根节点
        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal);
        if (postorder.length == 1) {
            return root;
        }
        //2、找到中序数组的切割点，后序数组切割点为最后一个结点
        int splitIndex;
        for (splitIndex = 0; splitIndex < inorder.length; splitIndex++) {
            if (inorder[splitIndex] == rootVal) {
                break;
            }
        }
        //3、按照根节点分割中序数组（分割成中序左数组和中序右数组）
        int[] inorderLeft = Arrays.copyOfRange(inorder, 0, splitIndex);
        int[] inorderRight = Arrays.copyOfRange(inorder, splitIndex + 1, inorder.length);
        //4、按照根节点分割后序数组（分割成后序左数组和后序右数组）
        int[] postorderLeft = Arrays.copyOfRange(postorder, 0, splitIndex);
        int[] postorderRight = Arrays.copyOfRange(postorder, splitIndex, postorder.length);
        //5、递归  中序左数组和后序左数组       中序右数组和后序右数组
        root.left = buildTree(inorderLeft,postorderLeft);
        root.right = buildTree(inorderRight, postorderRight);
        return root;
    }

    public static TreeNode buildTree1(int[] inorder, int[] postorder) {
        return traversal(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    /**
     * 递归优化 使用索引来进行分割  后序区间索引[inorderLeft,inorderRight)  后序区间[postorderLeft,postorderRight)
     * @param inorder
     * @param inorderLeft
     * @param inorderRight
     * @param postorder
     * @param postorderLeft
     * @param postorderRight
     * @return
     */
    public static TreeNode traversal(int[] inorder, int inorderLeft, int inorderRight, int[] postorder, int postorderLeft, int postorderRight) {
        if (inorderRight - inorderLeft == 0) {
            return null;
        }
        //1、后序数组最后一个结点作为根节点
        int rootVal = postorder[postorderRight - 1];
        TreeNode root = new TreeNode(rootVal);
        if (postorderRight - postorderLeft == 1) {
            return root;
        }
        System.out.println();
        //2、找到中序数组的切割点，后序数组切割点为最后一个结点
        int splitIndex;
        for (splitIndex = inorderLeft; splitIndex < inorderRight; splitIndex++) {
            if (inorder[splitIndex] == rootVal) {
                break;
            }
        }
        //3、按照根节点分割中序数组（分割成中序左数组和中序右数组）
        int inorderLeftBegin = inorderLeft;
        int inorderLeftEnd = splitIndex;
        int inorderRightBegin = splitIndex + 1;
        int inorderRightEnd = inorderRight;
        //4、按照根节点分割后序数组（分割成后序左数组和后序右数组）
        int postorderLeftBegin = postorderLeft;
        System.out.println(postorderLeft+"   "+inorderLeft);
        //如果postorderleft最开始不是从0开始，则需要加上中序左数组区间大小的size
        int postorderLeftEnd = postorderLeft + splitIndex - inorderLeft;
        int postorderRightBegin = postorderLeft + splitIndex - inorderLeft;
        int postorderRightEnd = postorderRight - 1;
        //5、递归  中序左数组和后序左数组       中序右数组和后序右数组
        root.left = traversal(inorder, inorderLeftBegin, inorderLeftEnd, postorder, postorderLeftBegin, postorderLeftEnd);
        root.right = traversal(inorder, inorderRightBegin, inorderRightEnd, postorder, postorderRightBegin, postorderRightEnd);
        return root;
    }

    public static void main(String[] args) {
        int[] a={9,3,15,20,7};
        int[] b={9,15,7,20,3};
        buildTree1(a,b);
    }

}
